Section: New Results
Improved complexity bounds for counting points on hyperelliptic curves
Participants : Simon Abelard, Pierrick Gaudry [contact] , Pierre-Jean Spaenlehauer [contact] .
In [3], we presented a probabilistic Las Vegas algorithm for computing the local zeta function of a hyperelliptic curve of genus defined over . It is based on the approaches by Schoof and Pila combined with a modeling of the -torsion by structured polynomial systems. Our main result improves on previously known complexity bounds by showing that there exists a constant such that, for any fixed , this algorithm has expected time and space complexity as grows and the characteristic is large enough.